package com.mlh.dp.打家劫舍;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author 缪林辉
 * @date 2024/4/22 10:09
 * @DESCRIPTION
 */
// 小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
// 除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，
// 聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。
// 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
// 给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
// 输入: root = [3,2,3,null,3,null,1]
// 输出: 7
// 解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7
public class 打家劫舍3 {

    //首先想到中序遍历之后就变成打家劫舍问题了   思路错了
    //总结，很多问题要从叶子节点开始处理，不断往上递归处理，这时候要用到的遍历就是后序遍历
    //本题目所有方法，都是看代码随想录写出
    public int method1(TreeNode root) {
        // return method1Aux(root);
        int[] res = method3(root);
        return Math.max(res[0],res[1]);
    }

    //递归方法的含义：返回以node为根节点 小偷能偷到钱的最大值
    public int method1Aux(TreeNode node){
        if(node==null){
            return 0;
        }
        if(node.left==null&&node.right==null){
            return node.val;
        }
        int v1=node.val,v2=0;
        if(node.left!=null){
            v1+= method1Aux(node.left.left)+method1Aux(node.left.right);
            v2+=method1Aux(node.left);
        }
        if(node.right!=null){
            v1+=method1Aux(node.right.left)+method1Aux(node.right.right);
            v2+=method1Aux(node.right);
        }
        return Math.max(v1,v2);
    }

    //记忆化搜索
    //利用map数组来记录已经遍历过节点的最大值
    Map<TreeNode,Integer>map=new HashMap<>();
    public int method2(TreeNode node){
        if(node==null){
            return 0;
        }
        if(node.left==null&&node.right==null){
            return node.val;
        }
        if(map.containsKey(node)){
            return map.get(node);
        }
        int v1=node.val,v2=0;
        if(node.left!=null){
            v1+= method1Aux(node.left.left)+method1Aux(node.left.right);
            v2+=method1Aux(node.left);
        }
        if(node.right!=null){
            v1+=method1Aux(node.right.left)+method1Aux(node.right.right);
            v2+=method1Aux(node.right);
        }
        int max=Math.max(v1,v2);
        map.put(node,max);
        return max;
    }

    //树形dp 直接去看代码随想录
    public int[] method3(TreeNode node){
        if(node==null){
            return new int[2];
        }
        int []left=method3(node.left);
        int []right=method3(node.right);
        int[]val=new int[2];
        val[0]= node.val+left[1]+right[1];
        val[1]= Math.max(right[0],right[1])+Math.max(left[0],left[1]);
        return val;
    }


    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    //树形dp
    // 参数 返回值
    //递归头
    //确定遍历顺序
    public int[] practice(TreeNode node){
        if(node==null){
            return new int[2];
        }
        int[] left = practice(node.left);
        int[] right = practice(node.right);
        int[] res=new int[2];
        res[0]=left[1]+right[1]+node.val;
        res[1]=Math.max(right[0],right[1])+Math.max(left[0],left[1]);
        return res;
    }
}
